/**
 此法超时
 * @param {number[]} nums
 * @return {boolean}
 */
export var find132pattern = function (nums) {
  let minIdx = 0,
    len = nums.length,
    stack = []
  while (minIdx < len) {
    stack = []
    for (let i = minIdx; i < len; i++) {
      if (!stack.length) stack[0] = nums[i]
      if (nums[i] > stack[0] && stack.length === 1) stack[1] = nums[i]
      if (nums[i] > stack[1] && stack.length === 2 && i !== len - 1) stack[1] = nums[i]
      if (nums[i] > stack[0] && nums[i] < stack[1]) return true
      if (minIdx === len - 2) return false
    }
    minIdx++
  }
  return false
}

/**
  单调栈
 * @param {number[]} nums
 * @return {boolean}
 */
export var find132pattern2 = function (nums) {
  let n = nums.length
  if (n < 3) return false
  const stack = [nums[n - 1]] // 单调栈,用于记录132中的3
  let last = -Infinity // 记录132中为2的元素
  for (let i = n - 2; i >= 0; i--) {
    const num = nums[i]
    // num < last 说明找到132中的1
    if (num < last) return true
    // num大于栈顶元素, 把 栈顶元素出栈作为132中的2, 而num则为3
    while (stack.length && num > stack[stack.length - 1]) last = stack.pop()
    stack.push(num)
  }
  return false
}

export var find132pattern3 = function (nums) {
  const n = nums.length
  const candidateI = [nums[0]],
    candidateJ = [nums[0]]

  for (let k = 1; k < n; ++k) {
    const idxI = binarySearchFirst(candidateI, nums[k])
    const idxJ = binarySearchLast(candidateJ, nums[k])
    if (idxI >= 0 && idxJ >= 0) {
      if (idxI <= idxJ) {
        return true
      }
    }

    if (nums[k] < candidateI[candidateI.length - 1]) {
      candidateI.push(nums[k])
      candidateJ.push(nums[k])
    } else if (nums[k] > candidateJ[candidateJ.length - 1]) {
      const lastI = candidateI[candidateI.length - 1]
      while (candidateJ.length && nums[k] > candidateJ[candidateJ.length - 1]) {
        candidateI.pop()
        candidateJ.pop()
      }
      candidateI.push(lastI)
      candidateJ.push(nums[k])
    }
  }

  return false
}

const binarySearchFirst = (candidate, target) => {
  let low = 0,
    high = candidate.length - 1
  if (candidate[high] >= target) {
    return -1
  }
  while (low < high) {
    const mid = Math.floor((high - low) / 2) + low
    const num = candidate[mid]
    if (num >= target) {
      low = mid + 1
    } else {
      high = mid
    }
  }
  return low
}

const binarySearchLast = (candidate, target) => {
  let low = 0,
    high = candidate.length - 1
  if (candidate[low] <= target) {
    return -1
  }
  while (low < high) {
    const mid = Math.floor((high - low + 1) / 2) + low
    const num = candidate[mid]
    if (num <= target) {
      high = mid - 1
    } else {
      low = mid
    }
  }
  return low
}
